/*
求全排列
*/

#include<iostream>
#include<vector>
using namespace std;

// 在s的位置j插入i
vector<int> Insert(vector<int> s, int i, int j)
{
	// 求出插入位置
	vector<int>::iterator it = s.begin()+j;
	
	// 插入整数i
	s.insert(it, i);
	return s;
}

// 在s集合中i-1到0位置插入i
vector<vector<int>> CreatePi(vector<int> s,int i)
{
	vector<vector<int>> tmp;
	
	// 在s(含i-1个整数)的每个位置插入i
	for (int j=s.size(); j>=0; j--)
	{
		// 在s的位置j插入i
		vector<int> s1 = Insert(s, i, j);
		
		// 添加到Pi中
		tmp.push_back(s1);
	}
	return tmp;
}

/* 迭代算法 */ 
// 迭代法求1-n的全排列
vector<vector<int>> Perm1(int n)
{
	// 存放1～i的全排列
	vector<vector<int>> Pi;
	Pi.push_back({1});
	
	// 存放1～i-1的全排列
	vector<vector<int>> Pi_1;
	
	// 循环添加2～n
	for (int i=2; i<=n; i++)
	{
		// 新值取代旧值
		Pi_1=Pi;
		Pi.clear();
		
		for (auto it=Pi_1.begin(); it!=Pi_1.end(); it++)
		{
			// 在it集合中插入i得到tmp
			vector<vector<int>> tmp = CreatePi(*it,i);
			
			// 将tmp的全部元素添加到Pi中
			for(int k=0;k<tmp.size();k++)
				Pi.push_back(tmp[k]);
		}
	}
 	return Pi;
}

/* 递归算法 */ 
// 递归算法
vector<vector<int>> perm(int n, int i)
{
	// 递归结束出口
	if(i==1)
		return {{1}};
	
	else
	{
		vector<vector<int>> Pi;
		vector<vector<int>> Pi_1 = perm(n, i-1);
		
		// 求出Pi_1 
		for (auto it=Pi_1.begin(); it!=Pi_1.end(); it++)
		{
			// 在it集合中插入i得到tmp
			vector<vector<int>> tmp=CreatePi(*it, i);
			
			// 将tmp的全部元素添加到Pi中
			for(int k=0; k<tmp.size(); k++)
				Pi.push_back(tmp[k]);
		}
		return Pi;
	}
}

// 递归法求1-n的全排列
vector<vector<int>> Perm2(int n)
{
	return perm(n, n);
}

// 打印全排列的结果
void disp(vector<vector<int>>&ans)
{
	printf("    ");
	for(auto it=ans.begin(); it!=ans.end(); it++)
	{
		for(int j=0; j<(*it).size(); j++)
			printf("%d",(*it)[j]);
		printf("  ");
	}
	printf("\n");
}

int main()
{
	// 初始化n值
	int n=3;
	
	// 存储全排列
	vector<vector<int>> ans;
	
	printf("1-%d的全排列如下:\n  ",n); 
	printf("解法1\n"); 
	ans = Perm1(n); 
	disp(ans); // 打印
	
	printf("解法2\n"); 
	ans = Perm2(n); 
	disp(ans); // 打印

	return 0;
}
